package correct.day7;

public class Test22 {

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] vis;
    static int m, n;
    public static int solve (char[][] grid) {
        // write code here
        m = grid.length;
        n = grid[0].length;
        vis = new boolean[m][n];
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1' && vis[i][j] == false) {
                    dfs(grid,i,j);
                    ret++;
                }
            }
        }
        return ret;
    }

    public static void dfs(char[][] grid, int a, int b) {
        vis[a][b] = true;
        for(int i = 0; i < 4; i++) {
            int x = a + dx[i];
            int y = b + dy[i];
            if(x>=0 && x<m && y>=0 && y<n && vis[x][y] == false && grid[x][y]=='1') {
                dfs(grid, x, y);
            }
        }
    }

    public static void main(String[] args) {
        char[][] arr = {{'1', '1', '0', '0', '0'}, {'0', '1', '0', '1', '1'}, {'0', '0', '0', '1', '1'}, {'0', '0', '0', '0', '0'}, {'0', '0', '1', '1', '1'}};
        System.out.println(solve(arr));
    }
}
